{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Seconds to Equalize a Circular Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumSeconds"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使循环数组所有元素相等的最少秒数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始长度为 <code>n</code>&nbsp;的数组&nbsp;<code>nums</code>&nbsp;。</p>\n",
    "\n",
    "<p>每一秒，你可以对数组执行以下操作：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>对于范围在&nbsp;<code>[0, n - 1]</code>&nbsp;内的每一个下标&nbsp;<code>i</code>&nbsp;，将&nbsp;<code>nums[i]</code> 替换成&nbsp;<code>nums[i]</code>&nbsp;，<code>nums[(i - 1 + n) % n]</code>&nbsp;或者&nbsp;<code>nums[(i + 1) % n]</code>&nbsp;三者之一。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>注意</strong>，所有元素会被同时替换。</p>\n",
    "\n",
    "<p>请你返回将数组 <code>nums</code>&nbsp;中所有元素变成相等元素所需要的 <strong>最少</strong>&nbsp;秒数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,2,1,2]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>我们可以在 1 秒内将数组变成相等元素：\n",
    "- 第 1 秒，将每个位置的元素分别变为 [nums[3],nums[1],nums[3],nums[3]] 。变化后，nums = [2,2,2,2] 。\n",
    "1 秒是将数组变成相等元素所需要的最少秒数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2,1,3,3,2]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>我们可以在 2 秒内将数组变成相等元素：\n",
    "- 第 1 秒，将每个位置的元素分别变为 [nums[0],nums[2],nums[2],nums[2],nums[3]] 。变化后，nums = [2,3,3,3,3] 。\n",
    "- 第 2 秒，将每个位置的元素分别变为 [nums[1],nums[1],nums[2],nums[3],nums[4]] 。变化后，nums = [3,3,3,3,3] 。\n",
    "2 秒是将数组变成相等元素所需要的最少秒数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [5,5,5,5]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>不需要执行任何操作，因为一开始数组中的元素已经全部相等。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n == nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-seconds-to-equalize-a-circular-array](https://leetcode.cn/problems/minimum-seconds-to-equalize-a-circular-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-seconds-to-equalize-a-circular-array](https://leetcode.cn/problems/minimum-seconds-to-equalize-a-circular-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,1,2]', '[2,1,3,3,2]', '[5,5,5,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ids = [i for i in range(n)]\n",
    "        z = sorted(list(zip(nums,ids)))\n",
    "        i,j,k,a = 0,0,0,999999\n",
    "        while i<n:\n",
    "            k,j = 0,i+1\n",
    "            while j<n and z[i][0]==z[j][0]:\n",
    "                k = max(k,(z[j][1] - z[j-1][1])//2)\n",
    "                j += 1\n",
    "            k = max(k,(z[i][1] + n - z[j-1][1])//2)\n",
    "            a = min(a,k)\n",
    "            i = j\n",
    "        \n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        c=Counter(nums)\n",
    "        if len(c)==1:return 0\n",
    "        n=len(nums)\n",
    "        ans=n//2\n",
    "        d=dict()\n",
    "        for i,x in enumerate(nums):\n",
    "            if c[x]==1:\n",
    "                if x in d:\n",
    "                    p,s,dis=d[x]\n",
    "                    d[x]=(i,s,max(dis,i-p,s+n-i))\n",
    "                    c[x]-=1\n",
    "            else:\n",
    "                if x not in d:\n",
    "                    d[x]=(i,i,0)\n",
    "                    c[x]-=1\n",
    "                else:\n",
    "                    p,s,dis=d[x]\n",
    "                    d[x]=(i,s,max(dis,i-p))\n",
    "                    c[x]-=1\n",
    "        # print(d)\n",
    "        for k,(p,s,dis) in d.items():\n",
    "            ans=min(ans,dis//2)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans={}\n",
    "        mp={}\n",
    "        for i in range(n):\n",
    "            if nums[i] in mp:\n",
    "                ans[nums[i]]=max(ans[nums[i]],(i-mp[nums[i]])//2) if nums[i] in ans else (i-mp[nums[i]])//2\n",
    "            mp[nums[i]]=i\n",
    "        st=set()\n",
    "        for i in range(n):\n",
    "            if nums[i] in mp and mp[nums[i]]>i and nums[i] not in st:\n",
    "                # print(mp[nums[i]],i)\n",
    "                ans[nums[i]]=max(ans[nums[i]],(n+i-mp[nums[i]])//2) if nums[i] in ans else (n+i-mp[nums[i]])//2\n",
    "                st.add(nums[i])\n",
    "        # print(ans)\n",
    "        return min(ans[a] for a in ans) if len(ans) else n//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        mark = [-1] * n\n",
    "        cnt = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            if num in cnt:\n",
    "                mark[i] = cnt[num]\n",
    "            cnt[num] = i\n",
    "        \n",
    "        for i, point in enumerate(mark):\n",
    "            if point == -1:\n",
    "                mark[i] = cnt[nums[i]]\n",
    "        print(mark)\n",
    "        choose = [False] * n\n",
    "        res = inf\n",
    "        for i, j in enumerate(mark):\n",
    "            if choose[i]:\n",
    "                continue\n",
    "            ans = n // 2 if i == j else 0\n",
    "            i1 = i\n",
    "            j1 = j\n",
    "            while choose[i1] == False:\n",
    "                if i1 < j1:\n",
    "                    mid = ((i1 + n - j1 - 1) + 1) // 2\n",
    "                else:\n",
    "                    mid = ((i1 - j1 - 1) + 1) // 2\n",
    "                ans = max(ans, mid)\n",
    "                choose[i1] = True\n",
    "                i1 = j1\n",
    "                j1 = mark[i1]\n",
    "                \n",
    "            res = min(res, ans)\n",
    "        return res\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        record={}\n",
    "        for i in range(len(nums)):\n",
    "            num=nums[i]\n",
    "            if num not in record.keys():\n",
    "                record[num]=(i,i,0)\n",
    "            else:\n",
    "                a,b,c=record[num]\n",
    "                temp=(i-b)//2\n",
    "                record[num]=(a,i,max(temp,c))\n",
    "        ans=len(nums)//2\n",
    "        for i in record.keys():\n",
    "            pos_first,pos_last,temp=record[i]\n",
    "            if pos_first !=pos_last:\n",
    "                pos_first+=len(nums)\n",
    "                temp=max(temp,(pos_first-pos_last)//2)\n",
    "                ans=min(ans,temp)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        lastoccur = defaultdict(int)\n",
    "        countstep = defaultdict(int)\n",
    "        for _ in range(2):\n",
    "            for i, num in enumerate(nums):\n",
    "                if num in lastoccur:\n",
    "\n",
    "                    step = (i + n - lastoccur[num]) % n\n",
    "\n",
    "                    if step == 0:\n",
    "                        step = n\n",
    "                        \n",
    "                    countstep[num] = max(countstep[num], step)\n",
    "                    lastoccur[num] = i\n",
    "                else:\n",
    "                    lastoccur[num] = i\n",
    "                \n",
    "        res = min(val for _, val in countstep.items())\n",
    "            \n",
    "                \n",
    "        return res // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        d = {}\n",
    "        for i, x in enumerate(nums):\n",
    "            if x in d:\n",
    "                a = d[x]\n",
    "                d[x] = (a[0], i, max(a[2], i - a[1]))\n",
    "            else:\n",
    "                d[x] = (i, i, 0)\n",
    "        res = n = len(nums)\n",
    "        for _, a in d.items():\n",
    "            res = min(res, max(a[2], a[0] + n - a[1]))\n",
    "        return res // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        last = {}\n",
    "        dic = defaultdict(int)\n",
    "        \n",
    "        for idx,num in enumerate(nums):\n",
    "            if num in last:\n",
    "                t = (idx - last[num] - 1 + 1) // 2\n",
    "                dic[num] = max(dic[num], t)\n",
    "            last[num] = idx\n",
    "            \n",
    "        \n",
    "        for idx,num in enumerate(nums):\n",
    "            if last[num] != -1:\n",
    "                t = (idx + n - last[num] - 1 + 1) // 2\n",
    "                dic[num] = max(dic[num], t)\n",
    "                last[num] = -1\n",
    "            \n",
    "        ans = 1_000_000_007\n",
    "        for num,val in dic.items():\n",
    "            ans = min(ans, val)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# min max\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dic = dict()\n",
    "        mx = defaultdict(int)\n",
    "        for i, x in enumerate(nums):\n",
    "            if x in dic:\n",
    "                mx[x] = max(mx[x], i - dic[x])\n",
    "                dic[x] = i\n",
    "            else:\n",
    "                dic[x] = i\n",
    "        for i, x in enumerate(nums):\n",
    "            if dic[x] == -1:\n",
    "                continue\n",
    "            if dic[x] == i:\n",
    "                mx[x] = n\n",
    "            if i < dic[x]:\n",
    "                mx[x] = max(mx[x], i + n - dic[x])\n",
    "                dic[x] = -1\n",
    "        # print(mx)\n",
    "        s = min(x for x in mx.values())\n",
    "        # print(s)\n",
    "        return s // 2\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        pos, steps, n = dict(), dict(), len(nums)\n",
    "        for i in range(n):\n",
    "            p = pos.get(nums[i], (-1, -1))\n",
    "            if p[0] != -1:\n",
    "                dist = (i - p[0]) // 2\n",
    "                steps[nums[i]] = max(steps.get(nums[i], 0), dist)\n",
    "            pos[nums[i]] = (i, i if p[1] == -1 else p[1])\n",
    "        \n",
    "        ans = n\n",
    "        for type, p in pos.items():\n",
    "            ans = min(ans, max(steps.get(type, 0), (p[1] + n - p[0]) // 2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = n\n",
    "        p = {}\n",
    "        for i in range(n):\n",
    "            if nums[i] not in p:\n",
    "                p[nums[i]] = []\n",
    "            p[nums[i]].append(i)\n",
    "        for v in p.values():\n",
    "            pans = 0\n",
    "            for i in range(len(v)):\n",
    "                k = (v[i] - v[i - 1] + n - 1) % n\n",
    "                pans = max(pans, (k + 1) // 2)\n",
    "            ans = min(ans, pans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        pre_pos = {}\n",
    "        first_pos = {}\n",
    "        max_dist = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            if num not in first_pos:\n",
    "                first_pos[num] = i\n",
    "            if num in pre_pos:\n",
    "                dist = i - pre_pos[num] - 1\n",
    "                if num in max_dist:\n",
    "                    max_dist[num] = max(max_dist[num], dist)\n",
    "                else:\n",
    "                    max_dist[num] = dist\n",
    "            pre_pos[num] = i\n",
    "        res = len(nums)\n",
    "        for num in nums:\n",
    "            dist = first_pos[num] + (len(nums) - pre_pos[num] - 1)\n",
    "            if num in max_dist:\n",
    "                dist = max(max_dist[num], dist)\n",
    "            res = min(res, (dist + 1) // 2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        cnt = dict()\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if cnt.get(nums[i]) != None:\n",
    "                cnt[nums[i]].append(i)\n",
    "            else:\n",
    "                cnt[nums[i]] = [i]\n",
    "            # cnt[nums[i]] = cnt.get(nums[i],[]).append(i)\n",
    "        \n",
    "        res = n\n",
    "        for x,y in cnt.items():\n",
    "            ans = 0\n",
    "            for i in range(1,len(y)):\n",
    "                ans = max(ans,y[i] - y[i-1]-1)\n",
    "            #print(x,y)\n",
    "            if len(y) == 1: ans = n - 1\n",
    "            else: ans = max(ans,y[0] + n - y[len(y)-1]-1)\n",
    "            res = min(res,(ans + 1) // 2)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        nums = nums + nums \n",
    "        hm = defaultdict(int)\n",
    "        last = dict()\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in last:\n",
    "                last[nums[i]] = i\n",
    "            else:\n",
    "                hm[nums[i]] = max(hm[nums[i]], i - last[nums[i]] - 1)\n",
    "                last[nums[i]] = i\n",
    "\n",
    "        res = 1 << 60\n",
    "        for k in hm:\n",
    "            res = min((hm[k] + 1) // 2, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        nums = nums * 2\n",
    "        d = {}\n",
    "        ans = defaultdict(int)\n",
    "        for i, num in enumerate(nums):\n",
    "            if num not in d:\n",
    "                d[num] = i\n",
    "            else:\n",
    "                ans[num] = max(ans[num], math.ceil((i - d[num] - 1) / 2))\n",
    "                d[num] = i\n",
    "\n",
    "        return min(ans.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        d = defaultdict(int)\n",
    "        d2 = defaultdict(list)\n",
    "        for i in range(len(nums)):\n",
    "            if d2[nums[i]]:\n",
    "                d[nums[i]] = max(i + 1 - d2[nums[i]][-1], d[nums[i]])\n",
    "            d2[nums[i]].append(i + 1)\n",
    "        ans = n\n",
    "        for key in d:\n",
    "            if len(d2[key]) > 1:\n",
    "                d[key] = max(d2[key][0] + n - d2[key][-1], d[key])\n",
    "                # print(key, d[key])\n",
    "                ans = min(ans, d[key])\n",
    "        return ans // 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        dic=defaultdict(list)\n",
    "        n=len(nums)\n",
    "        ans=1000000\n",
    "        for  i in range(n):\n",
    "            dic[nums[i]].append(i)\n",
    "        for idx in dic.values():\n",
    "            #print(idx)\n",
    "            temp=(n-1-idx[-1]+idx[0])\n",
    "            for  i in range(1,len(idx)):\n",
    "                temp=max(temp,idx[i]-idx[i-1]-1)\n",
    "            ans=min(temp,ans)\n",
    "        return (ans+1)//2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# 1 2 1 2 1 3 3 3 3 3 3 1 2 1 2 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        last = {}\n",
    "        dist = defaultdict(int)\n",
    "\n",
    "        n = len(nums)\n",
    "        for i in range(n << 1):\n",
    "            v = nums[i if i < n else i - n]\n",
    "            if v in last:\n",
    "                dist[v] = max(dist[v], i - last[v])\n",
    "            last[v] = i\n",
    "        \n",
    "        return min(dist.values()) >> 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        cnt = collections.defaultdict(list)\n",
    "        for i,ele in enumerate(nums):\n",
    "            cnt[ele].append(i)\n",
    "        \n",
    "        res = len(nums)\n",
    "        for key,pos in cnt.items():\n",
    "            #print(pos)\n",
    "            n = len(pos)\n",
    "            tmp = (len(nums)-1-pos[-1]+pos[0])//2 + (len(nums)-1-pos[-1]+pos[0])%2\n",
    "            for i in range(1,n,1):\n",
    "                #print((pos[i]-pos[i-1]-1)//2, (pos[i]-pos[i-1]-1)%2)\n",
    "                tmp =max(tmp,  (pos[i]-pos[i-1]-1)//2+(pos[i]-pos[i-1]-1)%2)\n",
    "            print(pos,tmp)\n",
    "            res = min(res,tmp)\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        map1=defaultdict(list)\n",
    "        n=len(nums)\n",
    "        res=n//2\n",
    "        for i in range(n):\n",
    "            map1[nums[i]].append(i)\n",
    "        for k,v in map1.items():\n",
    "            left=v[0]\n",
    "            maxl=0\n",
    "            for i in range(len(v)):\n",
    "                maxl=max(maxl,v[i]-left)\n",
    "                left=v[i]\n",
    "            maxl=max(maxl,n+v[0]-left)\n",
    "            res=min(res,(maxl)//2) #1 0 2 1 3 2 4 2\n",
    "        return res\n",
    "                \n",
    "                \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        \n",
    "        index = defaultdict(list)\n",
    "        \n",
    "        for i, num in enumerate(nums):\n",
    "            index[num].append(i)\n",
    "        \n",
    "        \n",
    "        t = float('inf')\n",
    "        for vals in index.values():\n",
    "            gap = 0\n",
    "            for i in range(1, len(vals)):\n",
    "                gap = max(gap, abs(vals[i] - vals[i - 1]))\n",
    "            gap = max(gap, len(nums) - vals[-1] + vals[0])\n",
    "            t= min(gap, t)\n",
    "        t -= 1\n",
    "        \n",
    "        print(t)\n",
    "        if t % 2:\n",
    "            return t // 2 + 1\n",
    "        return t // 2\n",
    "        # return math.ceil(gap / 2)\n",
    "        \n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        # can we assume the most common number needs to get spanned?\n",
    "        # no, for each index we find where its next identical number is\n",
    "        # that takes // 2 distance\n",
    "        # for each number we do the same\n",
    "        c = {}\n",
    "        for i, n in enumerate(nums):\n",
    "            if n not in c:\n",
    "                c[n] = []\n",
    "            c[n].append(i)\n",
    "        if len(c) <= 1:\n",
    "            return 0\n",
    "        final_res = 99999\n",
    "        for l in c.values():            \n",
    "            res = 0\n",
    "            for i in range(1, len(l)):\n",
    "                res = max(res, l[i] - l[i-1] - 1)\n",
    "            res = max(res, (len(nums) - 1 - l[-1] + l[0]))\n",
    "            # print(res)\n",
    "            final_res = min(res, final_res)\n",
    "        # print(c)\n",
    "                \n",
    "        return (final_res+1) // 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        pos = defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            pos[num].append(i)\n",
    "        ln = len(nums)\n",
    "        minsecs = ln//2\n",
    "        for v in pos.values():\n",
    "            if len(v)>1:\n",
    "                v.append(v[0]+ln)\n",
    "                minsecs = min(max((j-i)//2 for i, j in pairwise(v)), minsecs)\n",
    "        return minsecs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        n = len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            d[x].append(i)\n",
    "        \n",
    "        res = inf\n",
    "        for x in d:\n",
    "            arr = d[x]\n",
    "            v = 0\n",
    "            for i in range(len(arr)-1):\n",
    "                v = max(v, (arr[i+1] - arr[i] - 1))\n",
    "            v = max(v, (arr[0] + n - 1 - arr[-1]) )\n",
    "            # print(arr, v)\n",
    "            res = min(res, (v+1)//2)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "import math\n",
    "from typing import Optional, List\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(list)\n",
    "        for k, v in enumerate(nums):\n",
    "            m1[v].append(k)\n",
    "\n",
    "        def get_ans(ll):\n",
    "            if len(ll) == 1:\n",
    "                return math.ceil((len(nums) - 1) / 2)\n",
    "            ret = 0\n",
    "            for k, v in enumerate(ll):\n",
    "                if k == 0:\n",
    "                    v1 = math.ceil((len(nums) - 1 - ll[-1] + v) / 2)\n",
    "                    ret = max(ret, v1)\n",
    "                else:\n",
    "                    v1 = math.ceil((v - ll[k - 1] - 1) / 2)\n",
    "                    ret = max(ret, v1)\n",
    "            return ret\n",
    "        ans = math.inf\n",
    "        for i in m1:\n",
    "            llx = m1[i]\n",
    "            ans = min(ans, get_ans(llx))\n",
    "        return ans\n",
    "\n",
    "a = Solution()\n",
    "# [7,11,7,5]\n",
    "print(a.minimumSeconds([19,20,7,7,20]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        first,pre,pretime={},{},{}\n",
    "        n = len(nums)\n",
    "        ans = n//2\n",
    "        for i,v in enumerate(nums):\n",
    "            if v not in first:\n",
    "                first[v]=i\n",
    "                pretime[v]=0\n",
    "            else:\n",
    "                pretime[v] = max(pretime[v],(i-pre[v])//2)\n",
    "                ans = min(ans,max(pretime[v],(n-i+first[v])//2))\n",
    "            pre[v]=i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        dic = {} \n",
    "        for i in range(len(nums)) :\n",
    "            if nums[i] in dic: \n",
    "                dic[nums[i]].append(i)\n",
    "            else :\n",
    "                dic[nums[i]] = [i]\n",
    "        #print(\"dic is :\",dic)\n",
    "        rt = [inf]\n",
    "        for x,l in dic.items() :\n",
    "            mx = l[0] \n",
    "            for i in range(1,len(l)) :\n",
    "                mx = max(mx,l[i]-l[i-1]-1)\n",
    "            mx = max( mx,len(nums)-l[-1]+l[0]-1 )\n",
    "            rt.append(mx)\n",
    "        #print(rt)\n",
    "        mn = min(rt)\n",
    "        return (mn+1)//2\n",
    "                \n",
    "        \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        dis = {}\n",
    "        for i, num in enumerate(nums):\n",
    "            dis.setdefault(num, []).append(i)\n",
    "        n = len(nums)\n",
    "        res = n\n",
    "        for diss in dis.values():\n",
    "            diss.append(diss[0] + n)\n",
    "            mx = max((j-i)//2 for i, j in itertools.pairwise(diss))\n",
    "            res = min(res, mx)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        pos = defaultdict(list)\n",
    "        for i, x in enumerate(nums):\n",
    "            pos[x].append(i)\n",
    "        ans = n = len(nums)\n",
    "        \n",
    "        for a in pos.values():\n",
    "            a.append(a[0] + n) # 将第一个下标加入数组\n",
    "            mx = max((j - i) // 2 for i, j in pairwise(a))\n",
    "            ans = min(ans, mx)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 把问题看成是【扩散】元素\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        pos = defaultdict(list)\n",
    "        for i, x in enumerate(nums):\n",
    "            pos[x].append(i)\n",
    "\n",
    "        ans = n = len(nums)\n",
    "        for a in pos.values():\n",
    "            a.append(a[0] + n)\n",
    "            mx = max((j - i) // 2 for i, j in pairwise(a))\n",
    "            ans = min(ans, mx)\n",
    "            \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        pos, steps, n = defaultdict(lambda: (-1, -1)), defaultdict(int), len(nums)\n",
    "        for i in range(n):\n",
    "            pre, first = pos[nums[i]]\n",
    "            if pre != -1:\n",
    "                steps[nums[i]] = max(steps[nums[i]], (i - pre) // 2)\n",
    "            pos[nums[i]] = (i, i if first == -1 else first)\n",
    "\n",
    "        ans = n\n",
    "        for type, p in pos.items():\n",
    "            ans = min(ans, max(steps[type], (p[1] + n - p[0]) // 2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        tw_nums = nums * 2\n",
    "        group = defaultdict(list)\n",
    "        for i, x in enumerate(tw_nums):\n",
    "            group[x].append(i)\n",
    "        res = inf\n",
    "        for _, v in group.items():\n",
    "            mx = -inf\n",
    "            for i in range(1, len(v)):\n",
    "                mx = max(mx, (v[i] - v[i - 1]) // 2)\n",
    "            mx = max(mx, (v[0] + len(v) - v[-1]) // 2)\n",
    "            res = min(res, mx)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        tw_nums = nums * 2\n",
    "        group = defaultdict(list)\n",
    "        for i, x in enumerate(tw_nums):\n",
    "            group[x].append(i)\n",
    "        res = inf\n",
    "        for _, v in group.items():\n",
    "            mx = -inf\n",
    "            for x, y in pairwise(v):\n",
    "                mx = max(mx, (y - x) // 2)\n",
    "            res = min(res, mx)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        nums.extend(nums)\n",
    "        for i, v in enumerate(nums):\n",
    "            d[v].append(i)\n",
    "            \n",
    "        ans = len(nums)\n",
    "        for _, v in d.items():\n",
    "            max_dis = 0\n",
    "            for i in range(0, len(v) - 1):\n",
    "                max_dis = max(max_dis, (v[i + 1] - v[i]) // 2)\n",
    "            ans = min(ans, max_dis)\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pos = defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            pos[num].append(i)\n",
    "        \n",
    "        ans = n\n",
    "        for ls in pos.values():\n",
    "            ls.append(ls[0] + n)\n",
    "            mx = max((y - x) // 2 for x, y in pairwise(ls))\n",
    "            ans = min(ans, mx)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        # 最终所有的number都会变成一样的数字\n",
    "        # 而一个num只能变成相邻的数字，也就是说，确定了目标数字，并且得到距离自己最远的要传染的数字，就确定了秒数\n",
    "        # 最长的传染时间是两个最远的相同数字的距离，j - i // 2\n",
    "        pos = defaultdict(list)\n",
    "        for i, x in enumerate(nums):\n",
    "            pos[x].append(i)\n",
    "        ans = n = len(nums)\n",
    "        for a in pos.values():\n",
    "            a.append(a[0] + n) # 处理环形数组的情况\n",
    "            mx = max((j - i) // 2 for i, j in pairwise(a))\n",
    "            ans = min(ans, mx)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from itertools import pairwise\n",
    "# from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        pos = defaultdict(list)\n",
    "        for i, num in enumerate(nums):\n",
    "            pos[num].append(i)\n",
    "        res = n = len(nums)\n",
    "        for pos_list in pos.values():\n",
    "            pos_list.append(pos_list[0] + n)\n",
    "            tmp = max((j - i)//2 for i, j in pairwise(pos_list))\n",
    "            res = min(res, tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        nums = nums + nums\n",
    "        dic = defaultdict(list)\n",
    "        for i in range(len(nums)):\n",
    "            dic[nums[i]].append(i)\n",
    "        res = float('inf')\n",
    "        for v in dic.keys():\n",
    "            index = dic[v]\n",
    "            second = 0\n",
    "            for i in range(1,len(index)):\n",
    "                second = max(second,(index[i]-index[i-1])//2)\n",
    "            res = min(res,second)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict,deque\n",
    "from functools import cache\n",
    "import heapq\n",
    "from heapq import heappop,heappush \n",
    "from sortedcontainers import SortedDict,SortedList\n",
    "from itertools import pairwise\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = nums+nums\n",
    "        dic = defaultdict(list)\n",
    "        for i,a in enumerate(nums):\n",
    "            dic[a].append(i)\n",
    "        mx = n \n",
    "        for _,ls in dic.items():\n",
    "            tp = 0\n",
    "            for a,b in pairwise(ls):\n",
    "                tp = max(tp,(b-a)//2)\n",
    "            mx = min(mx,tp)\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minimumSeconds(self, nums: List[int]) -> int:\n",
    "#         if len(nums) == 1:\n",
    "#             return 0\n",
    "#         origin_cnt = {}\n",
    "#         for i,num in enumerate(nums):\n",
    "#             origin_cnt[num] = 1 if num not in origin_cnt else (origin_cnt[num] + 1)\n",
    "#             if nums[i - 1] == num:origin_cnt[num] += 1\n",
    "#             if nums[i + 1] == num:origin_cnt[num] += 1\n",
    "#         origin_cnt[nums[-1]] = 1 if nums[-1] not in origin_cnt else (origin_cnt[nums[-1]] + 1)\n",
    "#         select = sorted(origin_cnt.items(), key=lambda x:x[0], reverse= True)[0][0]\n",
    "#         second = 1\n",
    "#         cnt = 0\n",
    "#         not_changed = set()\n",
    "#         for i in range(len(nums) - 1):\n",
    "#             if nums[i - 1] == select or nums[i] == select or nums[i + 1] == select:\n",
    "#                 cnt += 1\n",
    "#                 nums[i] == select\n",
    "#             else:\n",
    "\n",
    "#         while cnt < len(nums):\n",
    "#             second += 1\n",
    "#             for i in \n",
    "# class Solution:\n",
    "#     def minimumSeconds(self, nums: List[int]) -> int:\n",
    "#         length = len(nums)\n",
    "#         if length == 1:\n",
    "#             return 0\n",
    "#         max_dis = {}\n",
    "#         for i in range(length):\n",
    "#             if nums[i] not in max_dis:\n",
    "#                 max_dis[nums[i]] = 0\n",
    "#             for j in range(i + 1, i + 1 + length):\n",
    "#                 if nums[i] == nums[j % length]:\n",
    "#                     max_dis[nums[i]] = max(j - i - 1, max_dis[nums[i]])\n",
    "#                     break\n",
    "#         return (sorted(max_dis.items(), key=lambda x:x[1])[0][1] + 1) // 2\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        if length == 1:\n",
    "            return 0\n",
    "        num_dic = {}\n",
    "        for i in range(length):\n",
    "            if nums[i] not in num_dic:\n",
    "                num_dic[nums[i]] = [i]\n",
    "            else:\n",
    "                num_dic[nums[i]].append(i)\n",
    "        min_res = length\n",
    "        for idxs in num_dic.values():\n",
    "            max_diff = 0\n",
    "            idxs.append(idxs[0] + length)\n",
    "            for i in range(len(idxs) - 1):\n",
    "                max_diff = max(max_diff, idxs[i + 1] - idxs[i])\n",
    "            min_res = min(max_diff, min_res)\n",
    "        return min_res // 2\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        # def func(k: int) -> int:\n",
    "        #     ans = 0\n",
    "        #     left = 0\n",
    "        #     n = len(nums)\n",
    "        #     while left < n:\n",
    "        #         if nums[left] == k: break\n",
    "        #         left += 1\n",
    "        #     m, right = left, left\n",
    "        #     while right < n:\n",
    "        #         if nums[right] == k:\n",
    "        #             ans = max(ans, (right - left) // 2)\n",
    "        #             left = right\n",
    "        #         right += 1\n",
    "        #     ans = max(ans, (m + n - left) // 2)\n",
    "        #     return ans\n",
    "        # 找到元素个数最多的元素\n",
    "        d = {}\n",
    "        for i, x in enumerate(nums):\n",
    "            if x in d:\n",
    "                d[x].append(i)\n",
    "            else:\n",
    "                d[x] = [i]\n",
    "        ans = inf\n",
    "        n = len(nums)\n",
    "        for key in d.keys():\n",
    "            v = d[key]\n",
    "            v.append(v[0] + n)\n",
    "            t = 0\n",
    "            for j in range(1, len(v)):\n",
    "                t = max(t, (v[j] - v[j - 1]) // 2)\n",
    "            ans = min(ans, t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: [int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=n+1\n",
    "\n",
    "        keys=nums+nums\n",
    "#        print(keys)\n",
    "        dc=defaultdict(int)            #dc[i]表示 两个i之间 间隔的最大值\n",
    "        left=defaultdict(int)          #left[i]表示上一个i出现的位置\n",
    "        ss=set()\n",
    "        for i in range(len(keys)):\n",
    "            if keys[i] in ss:\n",
    "                tmp=i-left[keys[i]]\n",
    "                dc[keys[i]]=max(dc[keys[i]], tmp)\n",
    "            else:\n",
    "                pass\n",
    "\n",
    "            left[keys[i]]=i\n",
    "            ss.add(keys[i])\n",
    "\n",
    "        maxed=len(keys)\n",
    "        for k,v in dc.items():\n",
    "            maxed=min(maxed,v)\n",
    "\n",
    "        return maxed//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        dic = {}\n",
    "        n = len(nums)\n",
    "        for i in range(2 * n):\n",
    "            if nums[i % n] in dic:\n",
    "                dic[nums[i % n]].append(i)\n",
    "            else:\n",
    "                dic[nums[i % n]] = [i]                \n",
    "        res = float(\"inf\")\n",
    "        for k, v in dic.items():\n",
    "            max_distance = -float(\"inf\")\n",
    "            for i in range(len(v) - 1):\n",
    "                distance = v[i+1] - v[i]\n",
    "                max_distance = max(max_distance, (distance)//2)\n",
    "                \n",
    "            res = min(res, max_distance)\n",
    "            \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "'''\n",
    "最终一定会变成x，x是nums中的某个数，因此我们可以穷举每一个可能的x，计算最小的变化次数\n",
    "\n",
    "变化次数的计算方法是\n",
    "\n",
    "如果是[2,3,4,2,3,2,2,2]\n",
    "比如这里选2我们要找到两个x间距的最远距离d\n",
    "\n",
    "最终返回最小的d的一半\n",
    "\n",
    "处理循环数组：将两个原始的长度为n数组拼接成一个2n长度的数组\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            nums.append(nums[i])\n",
    "        d={}\n",
    "        for i,x in enumerate(nums):\n",
    "            try:\n",
    "                d[x].append(i)\n",
    "            except:\n",
    "                d[x] = [i]\n",
    "        ans = inf \n",
    "        for key in d:\n",
    "            cnt = 0\n",
    "            for i in range(len(d[key])-1):\n",
    "                cnt = max(cnt,(d[key][i+1]-d[key][i])//2)\n",
    "            ans = min(ans,cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumSeconds(self, nums: List[int]) -> int:\n",
    "        hashTable = {}\n",
    "        # 记录元素下标\n",
    "        for i,x in enumerate(nums):\n",
    "            if x not in hashTable:\n",
    "                hashTable[x] = [i]\n",
    "            else:\n",
    "                hashTable[x].append(i)\n",
    "        ans = n = len(nums)\n",
    "        for i in hashTable.values():\n",
    "            time = 0\n",
    "            i.append(i[0] + n) # 这样就相当于是环形数组\n",
    "            for j in range(len(i) - 1):\n",
    "                time = max(time ,(i[j + 1] - i[j]) // 2)\n",
    "            ans = min(ans, time)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
